
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><title>Python: module gummworld2.quad_tree</title>
</head><body bgcolor="#f0f0f8">

<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="heading">
<tr bgcolor="#7799ee">
<td valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial">&nbsp;<br><big><big><strong><a href="gummworld2.html"><font color="#ffffff">gummworld2</font></a>.quad_tree</strong></big></big> (version $Id: quad_tree.py 248 2011-02-25 15:40:01Z stabbingfinger@gmail.com $)</font></td
><td align=right valign=bottom
><font color="#ffffff" face="helvetica, arial"><a href=".">index</a><br><a href="file:///C:/cygwin/home/bw/devel/python/svn/gummworld2/gamelib/gummworld2/quad_tree.py">c:\cygwin\home\bw\devel\python\svn\gummworld2\gamelib\gummworld2\quad_tree.py</a></font></td></tr></table>
    <p><tt>quad_tree.py&nbsp;-&nbsp;A&nbsp;quad&nbsp;tree&nbsp;implementation&nbsp;for&nbsp;pygame.<br>
&nbsp;<br>
Quick&nbsp;and&nbsp;dirty:<br>
&nbsp;&nbsp;&nbsp;&nbsp;<br>
&nbsp;&nbsp;&nbsp;&nbsp;#&nbsp;This&nbsp;code&nbsp;facsimile&nbsp;updates&nbsp;and&nbsp;draws&nbsp;the&nbsp;things&nbsp;that&nbsp;are&nbsp;on-screen.<br>
&nbsp;&nbsp;&nbsp;&nbsp;class&nbsp;ObjectWithRect(<a href="__builtin__.html#object">object</a>):<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def&nbsp;__init__(self):<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.<strong>rect</strong>&nbsp;=&nbsp;pygame.Rect(...)<br>
&nbsp;&nbsp;&nbsp;&nbsp;thing&nbsp;=&nbsp;ObjectWithRect()<br>
&nbsp;&nbsp;&nbsp;&nbsp;world&nbsp;=&nbsp;<a href="#QuadTree">QuadTree</a>(world_rect)<br>
&nbsp;&nbsp;&nbsp;&nbsp;world.add(thing)<br>
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;1:<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;things&nbsp;=&nbsp;world.entities_in(camera_rect)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;thing&nbsp;in&nbsp;things:<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;things_that_moved&nbsp;=&nbsp;update_list(things)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;thing&nbsp;in&nbsp;things_that_moved:<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;world.add(thing)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;draw_list(things)<br>
&nbsp;<br>
Thanks&nbsp;to:<br>
&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;&nbsp;&nbsp;Dylan&nbsp;J.&nbsp;Raub&nbsp;for&nbsp;his&nbsp;excellent&nbsp;pygame&nbsp;demo,&nbsp;Quadtree&nbsp;test,&nbsp;after&nbsp;which<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this&nbsp;module&nbsp;has&nbsp;been&nbsp;fundamentally&nbsp;modeled.&nbsp;Visit&nbsp;the&nbsp;project&nbsp;page:<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<a href="http://www.pygame.org/project-Quadtree+test-1691-.html">http://www.pygame.org/project-Quadtree+test-1691-.html</a>.<br>
&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;&nbsp;&nbsp;Jonathan&nbsp;Fararis&nbsp;for&nbsp;his&nbsp;excellent&nbsp;Quadtrees&nbsp;paper&nbsp;on&nbsp;gamedev.net.<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Original&nbsp;URL:&nbsp;<a href="http://www.gamedev.net/reference/programming/features/quadtrees/">http://www.gamedev.net/reference/programming/features/quadtrees/</a><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Archive&nbsp;URL:&nbsp;<a href="http://archive.gamedev.net/reference/programming/features/quadtrees/">http://archive.gamedev.net/reference/programming/features/quadtrees/</a></tt></p>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#aa55cc">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Modules</strong></big></font></td></tr>
    
<tr><td bgcolor="#aa55cc"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><table width="100%" summary="list"><tr><td width="25%" valign=top><a href="pygame.color.html">pygame.color</a><br>
</td><td width="25%" valign=top><a href="math.html">math</a><br>
</td><td width="25%" valign=top><a href="pygame.html">pygame</a><br>
</td><td width="25%" valign=top></td></tr></table></td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ee77aa">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Classes</strong></big></font></td></tr>
    
<tr><td bgcolor="#ee77aa"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><dl>
<dt><font face="helvetica, arial"><a href="__builtin__.html#object">__builtin__.object</a>
</font></dt><dd>
<dl>
<dt><font face="helvetica, arial"><a href="gummworld2.quad_tree.html#QuadTreeNode">QuadTreeNode</a>
</font></dt><dd>
<dl>
<dt><font face="helvetica, arial"><a href="gummworld2.quad_tree.html#QuadTree">QuadTree</a>
</font></dt></dl>
</dd>
</dl>
</dd>
</dl>
 <p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ffc8d8">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#000000" face="helvetica, arial"><a name="QuadTree">class <strong>QuadTree</strong></a>(<a href="gummworld2.quad_tree.html#QuadTreeNode">QuadTreeNode</a>)</font></td></tr>
    
<tr><td bgcolor="#ffc8d8"><tt>&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><dl><dt>Method resolution order:</dt>
<dd><a href="gummworld2.quad_tree.html#QuadTree">QuadTree</a></dd>
<dd><a href="gummworld2.quad_tree.html#QuadTreeNode">QuadTreeNode</a></dd>
<dd><a href="__builtin__.html#object">__builtin__.object</a></dd>
</dl>
<hr>
Methods defined here:<br>
<dl><dt><a name="QuadTree-__init__"><strong>__init__</strong></a>(self, rect, *entities, **kwargs)</dt><dd><tt><a href="#QuadTree">QuadTree</a>(rect,&nbsp;min_size=(128,128),&nbsp;worst_case=0,<br>
collide_rects=True,&nbsp;collide_entities=False,&nbsp;*entities)<br>
&nbsp;<br>
The&nbsp;<a href="#QuadTree">QuadTree</a>&nbsp;container&nbsp;efficiently&nbsp;stores&nbsp;objects,&nbsp;maintains<br>
collision&nbsp;info,&nbsp;and&nbsp;retrieves&nbsp;objects&nbsp;in&nbsp;an&nbsp;arbitrarily&nbsp;defined&nbsp;locale.<br>
&nbsp;<br>
The&nbsp;rect&nbsp;argument&nbsp;defines&nbsp;the&nbsp;quadtree's&nbsp;dimensions.<br>
&nbsp;<br>
The&nbsp;min_size&nbsp;argument&nbsp;defines&nbsp;the&nbsp;smallest&nbsp;quad&nbsp;size&nbsp;needed.&nbsp;The<br>
quadtree&nbsp;will&nbsp;be&nbsp;recursively&nbsp;subdivided&nbsp;until&nbsp;this&nbsp;limit&nbsp;is&nbsp;reached.<br>
&nbsp;<br>
The&nbsp;worst_case&nbsp;argument&nbsp;enables&nbsp;an&nbsp;enhancement&nbsp;to&nbsp;reduce&nbsp;the&nbsp;number&nbsp;of<br>
objects&nbsp;that&nbsp;default&nbsp;to&nbsp;level&nbsp;1.&nbsp;A&nbsp;value&nbsp;greater&nbsp;than&nbsp;zero&nbsp;enables&nbsp;this<br>
enhancement,&nbsp;and&nbsp;represents&nbsp;the&nbsp;amount&nbsp;to&nbsp;extend&nbsp;the&nbsp;quadtree's&nbsp;bounds<br>
on&nbsp;each&nbsp;side.<br>
&nbsp;<br>
The&nbsp;collide_rects&nbsp;argument&nbsp;sets&nbsp;the&nbsp;collision&nbsp;detection&nbsp;behavior&nbsp;that<br>
relies&nbsp;on&nbsp;the&nbsp;<a href="__builtin__.html#object">object</a>&nbsp;having&nbsp;a&nbsp;pygame.Rect&nbsp;instance&nbsp;variable.<br>
&nbsp;<br>
The&nbsp;collide_entities&nbsp;argument&nbsp;sets&nbsp;the&nbsp;collision&nbsp;detection&nbsp;behavior&nbsp;that<br>
relies&nbsp;on&nbsp;the&nbsp;<a href="__builtin__.html#object">object</a>&nbsp;having&nbsp;a&nbsp;collided&nbsp;instance&nbsp;variable,&nbsp;which&nbsp;is&nbsp;a<br>
staticmethod&nbsp;that&nbsp;takes&nbsp;two&nbsp;entities&nbsp;as&nbsp;arguments.<br>
&nbsp;<br>
The&nbsp;entities&nbsp;argument&nbsp;is&nbsp;the&nbsp;entities&nbsp;to&nbsp;add.<br>
&nbsp;<br>
<a href="#QuadTree">QuadTree</a>&nbsp;subclasses&nbsp;<a href="#QuadTreeNode">QuadTreeNode</a>.&nbsp;See&nbsp;the&nbsp;superclass&nbsp;for&nbsp;more&nbsp;methods.<br>
&nbsp;<br>
More&nbsp;detail&nbsp;on&nbsp;worst_case.&nbsp;Level&nbsp;1&nbsp;is&nbsp;expensive&nbsp;in&nbsp;terms&nbsp;of&nbsp;adding<br>
objects,&nbsp;since&nbsp;objects&nbsp;in&nbsp;level&nbsp;1&nbsp;are&nbsp;always&nbsp;involved&nbsp;in&nbsp;collisions<br>
detection,&nbsp;and&nbsp;many&nbsp;of&nbsp;those&nbsp;could&nbsp;be&nbsp;far&nbsp;away&nbsp;from&nbsp;the&nbsp;<a href="__builtin__.html#object">object</a>&nbsp;being<br>
added.&nbsp;As&nbsp;few&nbsp;as&nbsp;25&nbsp;objects&nbsp;in&nbsp;level&nbsp;1&nbsp;can&nbsp;double&nbsp;the&nbsp;number&nbsp;of<br>
collision&nbsp;checks&nbsp;per&nbsp;add.&nbsp;Without&nbsp;this&nbsp;enhancement,&nbsp;such&nbsp;objects&nbsp;are:<br>
those&nbsp;that&nbsp;straddle&nbsp;quad&nbsp;boundaries;&nbsp;those&nbsp;positioned&nbsp;outside&nbsp;the<br>
quadtree&nbsp;bounds.&nbsp;The&nbsp;size&nbsp;of&nbsp;worst_case&nbsp;doesn't&nbsp;affect&nbsp;the&nbsp;size&nbsp;of&nbsp;the<br>
quadtree&nbsp;bounding&nbsp;rect,&nbsp;and&nbsp;using&nbsp;excessively&nbsp;large&nbsp;values&nbsp;does&nbsp;not<br>
incur&nbsp;a&nbsp;performance&nbsp;penalty.&nbsp;However,&nbsp;this&nbsp;feature&nbsp;adds&nbsp;nine&nbsp;branches<br>
to&nbsp;level&nbsp;2&nbsp;that&nbsp;are&nbsp;recursively&nbsp;walked&nbsp;by&nbsp;the&nbsp;quadtree&nbsp;algorithms.&nbsp;The<br>
lowdown:&nbsp;for&nbsp;large&nbsp;numbers&nbsp;of&nbsp;objects&nbsp;it&nbsp;is&nbsp;worth&nbsp;turning&nbsp;on<br>
worst_case;&nbsp;for&nbsp;only&nbsp;a&nbsp;few&nbsp;objects&nbsp;or&nbsp;quadtrees&nbsp;with&nbsp;two&nbsp;levels&nbsp;the<br>
overhead&nbsp;of&nbsp;nine&nbsp;more&nbsp;branches&nbsp;may&nbsp;not&nbsp;be&nbsp;worthwhile.&nbsp;Lastly,&nbsp;this<br>
choice&nbsp;may&nbsp;only&nbsp;be&nbsp;of&nbsp;importance&nbsp;if&nbsp;trying&nbsp;to&nbsp;implement&nbsp;a&nbsp;quadtree&nbsp;on&nbsp;a<br>
wimpy&nbsp;platform.&nbsp;Try&nbsp;it&nbsp;both&nbsp;ways&nbsp;and&nbsp;check&nbsp;instance&nbsp;variables&nbsp;coll_tests<br>
and&nbsp;branch_visits_add&nbsp;after&nbsp;each&nbsp;game&nbsp;update&nbsp;to&nbsp;decide.</tt></dd></dl>

<dl><dt><a name="QuadTree-__iter__"><strong>__iter__</strong></a>(self)</dt></dl>

<dl><dt><a name="QuadTree-__len__"><strong>__len__</strong></a>(self)</dt></dl>

<dl><dt><a name="QuadTree-__zero__"><strong>__zero__</strong></a>(self)</dt></dl>

<dl><dt><a name="QuadTree-add"><strong>add</strong></a>(self, *entities)</dt><dd><tt>Add&nbsp;individual&nbsp;entities.</tt></dd></dl>

<dl><dt><a name="QuadTree-add_list"><strong>add_list</strong></a>(self, entities)</dt><dd><tt>Add&nbsp;a&nbsp;sequence&nbsp;of&nbsp;entities.</tt></dd></dl>

<dl><dt><a name="QuadTree-branch_of"><strong>branch_of</strong></a>(self, entity)</dt><dd><tt>Return&nbsp;the&nbsp;branch&nbsp;that&nbsp;contains&nbsp;entity.&nbsp;None&nbsp;is&nbsp;returned&nbsp;if&nbsp;entity&nbsp;is<br>
not&nbsp;in&nbsp;the&nbsp;quadtree.</tt></dd></dl>

<dl><dt><a name="QuadTree-collided"><strong>collided</strong></a>(self, left, right)</dt><dd><tt>This&nbsp;can&nbsp;be&nbsp;called&nbsp;externally,&nbsp;but&nbsp;usually&nbsp;not&nbsp;necessary.&nbsp;The<br>
quadtree&nbsp;automatically&nbsp;registers&nbsp;collisions&nbsp;as&nbsp;objects&nbsp;are&nbsp;added.&nbsp;This<br>
can&nbsp;be&nbsp;used&nbsp;on&nbsp;objects&nbsp;that&nbsp;are&nbsp;not&nbsp;currently&nbsp;in&nbsp;the&nbsp;quadtree.&nbsp;Note&nbsp;that<br>
each&nbsp;call&nbsp;to&nbsp;this&nbsp;method&nbsp;increments&nbsp;coll_tests.</tt></dd></dl>

<dl><dt><a name="QuadTree-collisions_dict"><strong>collisions_dict</strong></a>(self)</dt><dd><tt>Return&nbsp;a&nbsp;collision&nbsp;dict.&nbsp;The&nbsp;key&nbsp;is&nbsp;an&nbsp;entity,&nbsp;the&nbsp;value&nbsp;is&nbsp;a&nbsp;list&nbsp;of<br>
entities&nbsp;that&nbsp;the&nbsp;key&nbsp;collided&nbsp;with.<br>
&nbsp;<br>
Note:&nbsp;This&nbsp;method&nbsp;generates&nbsp;a&nbsp;new&nbsp;dict&nbsp;by&nbsp;iterating&nbsp;over<br>
<a href="#QuadTree">QuadTree</a>.collisions&nbsp;each&nbsp;time&nbsp;it&nbsp;is&nbsp;called.&nbsp;Try&nbsp;not&nbsp;to&nbsp;call&nbsp;it<br>
excessively,&nbsp;as&nbsp;it&nbsp;is&nbsp;potentially&nbsp;expensive.&nbsp;Also&nbsp;of&nbsp;note,&nbsp;the&nbsp;returned<br>
dict&nbsp;is&nbsp;invalid&nbsp;as&nbsp;soon&nbsp;as&nbsp;an&nbsp;entity&nbsp;is&nbsp;added&nbsp;to&nbsp;or&nbsp;removed&nbsp;from&nbsp;the<br>
quadtree.</tt></dd></dl>

<dl><dt><a name="QuadTree-entities_in"><strong>entities_in</strong></a>(self, rect)</dt><dd><tt>Return&nbsp;list&nbsp;of&nbsp;entities&nbsp;that&nbsp;collide&nbsp;with&nbsp;rect.</tt></dd></dl>

<dl><dt><a name="QuadTree-level_of"><strong>level_of</strong></a>(self, entity)</dt><dd><tt>Return&nbsp;the&nbsp;level&nbsp;the&nbsp;entity&nbsp;is&nbsp;on.&nbsp;None&nbsp;is&nbsp;returned&nbsp;if&nbsp;entity&nbsp;is&nbsp;not<br>
in&nbsp;the&nbsp;quadtree.</tt></dd></dl>

<dl><dt><a name="QuadTree-remove"><strong>remove</strong></a>(self, *entities)</dt><dd><tt>Remove&nbsp;individual&nbsp;entities.</tt></dd></dl>

<dl><dt><a name="QuadTree-remove_list"><strong>remove_list</strong></a>(self, entities)</dt><dd><tt>Remove&nbsp;a&nbsp;sequence&nbsp;of&nbsp;entities.</tt></dd></dl>

<dl><dt><a name="QuadTree-reset_counters"><strong>reset_counters</strong></a>(self)</dt><dd><tt>Reset&nbsp;the&nbsp;coll_tests&nbsp;and&nbsp;branch_visits_add&nbsp;to&nbsp;0.&nbsp;Call&nbsp;this&nbsp;once&nbsp;per<br>
game&nbsp;cycle&nbsp;if&nbsp;reporting&nbsp;usage&nbsp;metrics.</tt></dd></dl>

<hr>
Data descriptors defined here:<br>
<dl><dt><strong>collide_entities</strong></dt>
<dd><tt>Set&nbsp;True&nbsp;to&nbsp;use&nbsp;entity.collided&nbsp;in&nbsp;collision&nbsp;testing.</tt></dd>
</dl>
<dl><dt><strong>collide_rects</strong></dt>
<dd><tt>Set&nbsp;True&nbsp;to&nbsp;use&nbsp;entity.rect&nbsp;in&nbsp;collision&nbsp;testing.</tt></dd>
</dl>
<hr>
Methods inherited from <a href="gummworld2.quad_tree.html#QuadTreeNode">QuadTreeNode</a>:<br>
<dl><dt><a name="QuadTree-entities_per"><strong>entities_per</strong></a>(self, results)</dt><dd><tt>Recursively&nbsp;build&nbsp;a&nbsp;list&nbsp;of&nbsp;tuples&nbsp;in&nbsp;results.&nbsp;Each&nbsp;tuple&nbsp;contains<br>
the&nbsp;branch&nbsp;level,&nbsp;branch&nbsp;id,&nbsp;and&nbsp;number&nbsp;of&nbsp;entities.&nbsp;This&nbsp;is&nbsp;a&nbsp;debuggin/<br>
tuning&nbsp;aid.</tt></dd></dl>

<dl><dt><a name="QuadTree-test_collisions"><strong>test_collisions</strong></a>(self, entity)</dt><dd><tt>Kick&nbsp;off&nbsp;a&nbsp;recursive&nbsp;collision&nbsp;test&nbsp;starting&nbsp;with&nbsp;this&nbsp;node.&nbsp;It&nbsp;is<br>
usually&nbsp;not&nbsp;necessary&nbsp;to&nbsp;do&nbsp;this.&nbsp;It&nbsp;is&nbsp;done&nbsp;automatically&nbsp;when&nbsp;an<br>
entity&nbsp;is&nbsp;added.</tt></dd></dl>

<hr>
Data descriptors inherited from <a href="gummworld2.quad_tree.html#QuadTreeNode">QuadTreeNode</a>:<br>
<dl><dt><strong>__dict__</strong></dt>
<dd><tt>dictionary&nbsp;for&nbsp;instance&nbsp;variables&nbsp;(if&nbsp;defined)</tt></dd>
</dl>
<dl><dt><strong>__weakref__</strong></dt>
<dd><tt>list&nbsp;of&nbsp;weak&nbsp;references&nbsp;to&nbsp;the&nbsp;object&nbsp;(if&nbsp;defined)</tt></dd>
</dl>
<dl><dt><strong>is_leaf</strong></dt>
<dd><tt>True&nbsp;if&nbsp;this&nbsp;node&nbsp;is&nbsp;a&nbsp;leaf&nbsp;node&nbsp;(i.e.,&nbsp;has&nbsp;no&nbsp;branches).</tt></dd>
</dl>
<dl><dt><strong>is_root</strong></dt>
<dd><tt>True&nbsp;if&nbsp;this&nbsp;node&nbsp;is&nbsp;the&nbsp;root&nbsp;node.</tt></dd>
</dl>
<dl><dt><strong>path</strong></dt>
<dd><tt>Return&nbsp;a&nbsp;string&nbsp;indicating&nbsp;branch_id's&nbsp;along&nbsp;the&nbsp;path&nbsp;from&nbsp;the&nbsp;root<br>
to&nbsp;this&nbsp;branch.&nbsp;This&nbsp;is&nbsp;a&nbsp;debugging/tuning&nbsp;aid.</tt></dd>
</dl>
</td></tr></table> <p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ffc8d8">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#000000" face="helvetica, arial"><a name="QuadTreeNode">class <strong>QuadTreeNode</strong></a>(<a href="__builtin__.html#object">__builtin__.object</a>)</font></td></tr>
    
<tr><td bgcolor="#ffc8d8"><tt>&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%">Methods defined here:<br>
<dl><dt><a name="QuadTreeNode-__init__"><strong>__init__</strong></a>(self, parent, rect, branch_id<font color="#909090">=1</font>)</dt><dd><tt>Should&nbsp;be&nbsp;no&nbsp;need&nbsp;to&nbsp;manually&nbsp;construct&nbsp;these.&nbsp;The&nbsp;<a href="#QuadTree">QuadTree</a><br>
constructor&nbsp;does&nbsp;this&nbsp;automatically.</tt></dd></dl>

<dl><dt><a name="QuadTreeNode-entities_per"><strong>entities_per</strong></a>(self, results)</dt><dd><tt>Recursively&nbsp;build&nbsp;a&nbsp;list&nbsp;of&nbsp;tuples&nbsp;in&nbsp;results.&nbsp;Each&nbsp;tuple&nbsp;contains<br>
the&nbsp;branch&nbsp;level,&nbsp;branch&nbsp;id,&nbsp;and&nbsp;number&nbsp;of&nbsp;entities.&nbsp;This&nbsp;is&nbsp;a&nbsp;debuggin/<br>
tuning&nbsp;aid.</tt></dd></dl>

<dl><dt><a name="QuadTreeNode-test_collisions"><strong>test_collisions</strong></a>(self, entity)</dt><dd><tt>Kick&nbsp;off&nbsp;a&nbsp;recursive&nbsp;collision&nbsp;test&nbsp;starting&nbsp;with&nbsp;this&nbsp;node.&nbsp;It&nbsp;is<br>
usually&nbsp;not&nbsp;necessary&nbsp;to&nbsp;do&nbsp;this.&nbsp;It&nbsp;is&nbsp;done&nbsp;automatically&nbsp;when&nbsp;an<br>
entity&nbsp;is&nbsp;added.</tt></dd></dl>

<hr>
Data descriptors defined here:<br>
<dl><dt><strong>__dict__</strong></dt>
<dd><tt>dictionary&nbsp;for&nbsp;instance&nbsp;variables&nbsp;(if&nbsp;defined)</tt></dd>
</dl>
<dl><dt><strong>__weakref__</strong></dt>
<dd><tt>list&nbsp;of&nbsp;weak&nbsp;references&nbsp;to&nbsp;the&nbsp;object&nbsp;(if&nbsp;defined)</tt></dd>
</dl>
<dl><dt><strong>is_leaf</strong></dt>
<dd><tt>True&nbsp;if&nbsp;this&nbsp;node&nbsp;is&nbsp;a&nbsp;leaf&nbsp;node&nbsp;(i.e.,&nbsp;has&nbsp;no&nbsp;branches).</tt></dd>
</dl>
<dl><dt><strong>is_root</strong></dt>
<dd><tt>True&nbsp;if&nbsp;this&nbsp;node&nbsp;is&nbsp;the&nbsp;root&nbsp;node.</tt></dd>
</dl>
<dl><dt><strong>path</strong></dt>
<dd><tt>Return&nbsp;a&nbsp;string&nbsp;indicating&nbsp;branch_id's&nbsp;along&nbsp;the&nbsp;path&nbsp;from&nbsp;the&nbsp;root<br>
to&nbsp;this&nbsp;branch.&nbsp;This&nbsp;is&nbsp;a&nbsp;debugging/tuning&nbsp;aid.</tt></dd>
</dl>
</td></tr></table></td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#55aa55">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Data</strong></big></font></td></tr>
    
<tr><td bgcolor="#55aa55"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%"><strong>ACTIVEEVENT</strong> = 1<br>
<strong>ANYFORMAT</strong> = 268435456<br>
<strong>ASYNCBLIT</strong> = 4<br>
<strong>AUDIO_S16</strong> = 32784<br>
<strong>AUDIO_S16LSB</strong> = 32784<br>
<strong>AUDIO_S16MSB</strong> = 36880<br>
<strong>AUDIO_S16SYS</strong> = 32784<br>
<strong>AUDIO_S8</strong> = 32776<br>
<strong>AUDIO_U16</strong> = 16<br>
<strong>AUDIO_U16LSB</strong> = 16<br>
<strong>AUDIO_U16MSB</strong> = 4112<br>
<strong>AUDIO_U16SYS</strong> = 16<br>
<strong>AUDIO_U8</strong> = 8<br>
<strong>BIG_ENDIAN</strong> = 4321<br>
<strong>BLEND_ADD</strong> = 1<br>
<strong>BLEND_MAX</strong> = 5<br>
<strong>BLEND_MIN</strong> = 4<br>
<strong>BLEND_MULT</strong> = 3<br>
<strong>BLEND_RGBA_ADD</strong> = 6<br>
<strong>BLEND_RGBA_MAX</strong> = 16<br>
<strong>BLEND_RGBA_MIN</strong> = 9<br>
<strong>BLEND_RGBA_MULT</strong> = 8<br>
<strong>BLEND_RGBA_SUB</strong> = 7<br>
<strong>BLEND_RGB_ADD</strong> = 1<br>
<strong>BLEND_RGB_MAX</strong> = 5<br>
<strong>BLEND_RGB_MIN</strong> = 4<br>
<strong>BLEND_RGB_MULT</strong> = 3<br>
<strong>BLEND_RGB_SUB</strong> = 2<br>
<strong>BLEND_SUB</strong> = 2<br>
<strong>BUTTON_X1</strong> = 6<br>
<strong>BUTTON_X2</strong> = 7<br>
<strong>DOUBLEBUF</strong> = 1073741824<br>
<strong>FULLSCREEN</strong> = -2147483648<br>
<strong>GL_ACCELERATED_VISUAL</strong> = 15<br>
<strong>GL_ACCUM_ALPHA_SIZE</strong> = 11<br>
<strong>GL_ACCUM_BLUE_SIZE</strong> = 10<br>
<strong>GL_ACCUM_GREEN_SIZE</strong> = 9<br>
<strong>GL_ACCUM_RED_SIZE</strong> = 8<br>
<strong>GL_ALPHA_SIZE</strong> = 3<br>
<strong>GL_BLUE_SIZE</strong> = 2<br>
<strong>GL_BUFFER_SIZE</strong> = 4<br>
<strong>GL_DEPTH_SIZE</strong> = 6<br>
<strong>GL_DOUBLEBUFFER</strong> = 5<br>
<strong>GL_GREEN_SIZE</strong> = 1<br>
<strong>GL_MULTISAMPLEBUFFERS</strong> = 13<br>
<strong>GL_MULTISAMPLESAMPLES</strong> = 14<br>
<strong>GL_RED_SIZE</strong> = 0<br>
<strong>GL_STENCIL_SIZE</strong> = 7<br>
<strong>GL_STEREO</strong> = 12<br>
<strong>GL_SWAP_CONTROL</strong> = 16<br>
<strong>HAT_CENTERED</strong> = 0<br>
<strong>HAT_DOWN</strong> = 4<br>
<strong>HAT_LEFT</strong> = 8<br>
<strong>HAT_LEFTDOWN</strong> = 12<br>
<strong>HAT_LEFTUP</strong> = 9<br>
<strong>HAT_RIGHT</strong> = 2<br>
<strong>HAT_RIGHTDOWN</strong> = 6<br>
<strong>HAT_RIGHTUP</strong> = 3<br>
<strong>HAT_UP</strong> = 1<br>
<strong>HWACCEL</strong> = 256<br>
<strong>HWPALETTE</strong> = 536870912<br>
<strong>HWSURFACE</strong> = 1<br>
<strong>IYUV_OVERLAY</strong> = 1448433993<br>
<strong>JOYAXISMOTION</strong> = 7<br>
<strong>JOYBALLMOTION</strong> = 8<br>
<strong>JOYBUTTONDOWN</strong> = 10<br>
<strong>JOYBUTTONUP</strong> = 11<br>
<strong>JOYHATMOTION</strong> = 9<br>
<strong>KEYDOWN</strong> = 2<br>
<strong>KEYUP</strong> = 3<br>
<strong>KMOD_ALT</strong> = 768<br>
<strong>KMOD_CAPS</strong> = 8192<br>
<strong>KMOD_CTRL</strong> = 192<br>
<strong>KMOD_LALT</strong> = 256<br>
<strong>KMOD_LCTRL</strong> = 64<br>
<strong>KMOD_LMETA</strong> = 1024<br>
<strong>KMOD_LSHIFT</strong> = 1<br>
<strong>KMOD_META</strong> = 3072<br>
<strong>KMOD_MODE</strong> = 16384<br>
<strong>KMOD_NONE</strong> = 0<br>
<strong>KMOD_NUM</strong> = 4096<br>
<strong>KMOD_RALT</strong> = 512<br>
<strong>KMOD_RCTRL</strong> = 128<br>
<strong>KMOD_RMETA</strong> = 2048<br>
<strong>KMOD_RSHIFT</strong> = 2<br>
<strong>KMOD_SHIFT</strong> = 3<br>
<strong>K_0</strong> = 48<br>
<strong>K_1</strong> = 49<br>
<strong>K_2</strong> = 50<br>
<strong>K_3</strong> = 51<br>
<strong>K_4</strong> = 52<br>
<strong>K_5</strong> = 53<br>
<strong>K_6</strong> = 54<br>
<strong>K_7</strong> = 55<br>
<strong>K_8</strong> = 56<br>
<strong>K_9</strong> = 57<br>
<strong>K_AMPERSAND</strong> = 38<br>
<strong>K_ASTERISK</strong> = 42<br>
<strong>K_AT</strong> = 64<br>
<strong>K_BACKQUOTE</strong> = 96<br>
<strong>K_BACKSLASH</strong> = 92<br>
<strong>K_BACKSPACE</strong> = 8<br>
<strong>K_BREAK</strong> = 318<br>
<strong>K_CAPSLOCK</strong> = 301<br>
<strong>K_CARET</strong> = 94<br>
<strong>K_CLEAR</strong> = 12<br>
<strong>K_COLON</strong> = 58<br>
<strong>K_COMMA</strong> = 44<br>
<strong>K_DELETE</strong> = 127<br>
<strong>K_DOLLAR</strong> = 36<br>
<strong>K_DOWN</strong> = 274<br>
<strong>K_END</strong> = 279<br>
<strong>K_EQUALS</strong> = 61<br>
<strong>K_ESCAPE</strong> = 27<br>
<strong>K_EURO</strong> = 321<br>
<strong>K_EXCLAIM</strong> = 33<br>
<strong>K_F1</strong> = 282<br>
<strong>K_F10</strong> = 291<br>
<strong>K_F11</strong> = 292<br>
<strong>K_F12</strong> = 293<br>
<strong>K_F13</strong> = 294<br>
<strong>K_F14</strong> = 295<br>
<strong>K_F15</strong> = 296<br>
<strong>K_F2</strong> = 283<br>
<strong>K_F3</strong> = 284<br>
<strong>K_F4</strong> = 285<br>
<strong>K_F5</strong> = 286<br>
<strong>K_F6</strong> = 287<br>
<strong>K_F7</strong> = 288<br>
<strong>K_F8</strong> = 289<br>
<strong>K_F9</strong> = 290<br>
<strong>K_FIRST</strong> = 0<br>
<strong>K_GREATER</strong> = 62<br>
<strong>K_HASH</strong> = 35<br>
<strong>K_HELP</strong> = 315<br>
<strong>K_HOME</strong> = 278<br>
<strong>K_INSERT</strong> = 277<br>
<strong>K_KP0</strong> = 256<br>
<strong>K_KP1</strong> = 257<br>
<strong>K_KP2</strong> = 258<br>
<strong>K_KP3</strong> = 259<br>
<strong>K_KP4</strong> = 260<br>
<strong>K_KP5</strong> = 261<br>
<strong>K_KP6</strong> = 262<br>
<strong>K_KP7</strong> = 263<br>
<strong>K_KP8</strong> = 264<br>
<strong>K_KP9</strong> = 265<br>
<strong>K_KP_DIVIDE</strong> = 267<br>
<strong>K_KP_ENTER</strong> = 271<br>
<strong>K_KP_EQUALS</strong> = 272<br>
<strong>K_KP_MINUS</strong> = 269<br>
<strong>K_KP_MULTIPLY</strong> = 268<br>
<strong>K_KP_PERIOD</strong> = 266<br>
<strong>K_KP_PLUS</strong> = 270<br>
<strong>K_LALT</strong> = 308<br>
<strong>K_LAST</strong> = 323<br>
<strong>K_LCTRL</strong> = 306<br>
<strong>K_LEFT</strong> = 276<br>
<strong>K_LEFTBRACKET</strong> = 91<br>
<strong>K_LEFTPAREN</strong> = 40<br>
<strong>K_LESS</strong> = 60<br>
<strong>K_LMETA</strong> = 310<br>
<strong>K_LSHIFT</strong> = 304<br>
<strong>K_LSUPER</strong> = 311<br>
<strong>K_MENU</strong> = 319<br>
<strong>K_MINUS</strong> = 45<br>
<strong>K_MODE</strong> = 313<br>
<strong>K_NUMLOCK</strong> = 300<br>
<strong>K_PAGEDOWN</strong> = 281<br>
<strong>K_PAGEUP</strong> = 280<br>
<strong>K_PAUSE</strong> = 19<br>
<strong>K_PERIOD</strong> = 46<br>
<strong>K_PLUS</strong> = 43<br>
<strong>K_POWER</strong> = 320<br>
<strong>K_PRINT</strong> = 316<br>
<strong>K_QUESTION</strong> = 63<br>
<strong>K_QUOTE</strong> = 39<br>
<strong>K_QUOTEDBL</strong> = 34<br>
<strong>K_RALT</strong> = 307<br>
<strong>K_RCTRL</strong> = 305<br>
<strong>K_RETURN</strong> = 13<br>
<strong>K_RIGHT</strong> = 275<br>
<strong>K_RIGHTBRACKET</strong> = 93<br>
<strong>K_RIGHTPAREN</strong> = 41<br>
<strong>K_RMETA</strong> = 309<br>
<strong>K_RSHIFT</strong> = 303<br>
<strong>K_RSUPER</strong> = 312<br>
<strong>K_SCROLLOCK</strong> = 302<br>
<strong>K_SEMICOLON</strong> = 59<br>
<strong>K_SLASH</strong> = 47<br>
<strong>K_SPACE</strong> = 32<br>
<strong>K_SYSREQ</strong> = 317<br>
<strong>K_TAB</strong> = 9<br>
<strong>K_UNDERSCORE</strong> = 95<br>
<strong>K_UNKNOWN</strong> = 0<br>
<strong>K_UP</strong> = 273<br>
<strong>K_a</strong> = 97<br>
<strong>K_b</strong> = 98<br>
<strong>K_c</strong> = 99<br>
<strong>K_d</strong> = 100<br>
<strong>K_e</strong> = 101<br>
<strong>K_f</strong> = 102<br>
<strong>K_g</strong> = 103<br>
<strong>K_h</strong> = 104<br>
<strong>K_i</strong> = 105<br>
<strong>K_j</strong> = 106<br>
<strong>K_k</strong> = 107<br>
<strong>K_l</strong> = 108<br>
<strong>K_m</strong> = 109<br>
<strong>K_n</strong> = 110<br>
<strong>K_o</strong> = 111<br>
<strong>K_p</strong> = 112<br>
<strong>K_q</strong> = 113<br>
<strong>K_r</strong> = 114<br>
<strong>K_s</strong> = 115<br>
<strong>K_t</strong> = 116<br>
<strong>K_u</strong> = 117<br>
<strong>K_v</strong> = 118<br>
<strong>K_w</strong> = 119<br>
<strong>K_x</strong> = 120<br>
<strong>K_y</strong> = 121<br>
<strong>K_z</strong> = 122<br>
<strong>LIL_ENDIAN</strong> = 1234<br>
<strong>MOUSEBUTTONDOWN</strong> = 5<br>
<strong>MOUSEBUTTONUP</strong> = 6<br>
<strong>MOUSEMOTION</strong> = 4<br>
<strong>NOEVENT</strong> = 0<br>
<strong>NOFRAME</strong> = 32<br>
<strong>NUMEVENTS</strong> = 32<br>
<strong>OPENGL</strong> = 2<br>
<strong>OPENGLBLIT</strong> = 10<br>
<strong>PREALLOC</strong> = 16777216<br>
<strong>QUIT</strong> = 12<br>
<strong>RESIZABLE</strong> = 16<br>
<strong>RLEACCEL</strong> = 16384<br>
<strong>RLEACCELOK</strong> = 8192<br>
<strong>SCRAP_BMP</strong> = 'image/bmp'<br>
<strong>SCRAP_CLIPBOARD</strong> = 0<br>
<strong>SCRAP_PBM</strong> = 'image/pbm'<br>
<strong>SCRAP_PPM</strong> = 'image/ppm'<br>
<strong>SCRAP_SELECTION</strong> = 1<br>
<strong>SCRAP_TEXT</strong> = 'text/plain'<br>
<strong>SRCALPHA</strong> = 65536<br>
<strong>SRCCOLORKEY</strong> = 4096<br>
<strong>SWSURFACE</strong> = 0<br>
<strong>SYSWMEVENT</strong> = 13<br>
<strong>TIMER_RESOLUTION</strong> = 10<br>
<strong>USEREVENT</strong> = 24<br>
<strong>UYVY_OVERLAY</strong> = 1498831189<br>
<strong>VIDEOEXPOSE</strong> = 17<br>
<strong>VIDEORESIZE</strong> = 16<br>
<strong>YUY2_OVERLAY</strong> = 844715353<br>
<strong>YV12_OVERLAY</strong> = 842094169<br>
<strong>YVYU_OVERLAY</strong> = 1431918169<br>
<strong>__author__</strong> = 'Gummbum, (c) 2011'<br>
<strong>__version__</strong> = '$Id: quad_tree.py 248 2011-02-25 15:40:01Z stabbingfinger@gmail.com $'</td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#7799ee">
<td colspan=3 valign=bottom>&nbsp;<br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Author</strong></big></font></td></tr>
    
<tr><td bgcolor="#7799ee"><tt>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</tt></td><td>&nbsp;</td>
<td width="100%">Gummbum,&nbsp;(c)&nbsp;2011</td></tr></table>
</body></html>